//============================================================================
// Name               : sort.cpp
// Created on         : Apr 22, 2013
// Author             : Moisés Jardim Pinheiro
//============================================================================

#include <iostream>
#include <limits.h>
#include <algorithm>
extern "C" {
#include "utils.h"
}

using namespace std;

/**
 * Declaração da variável que receberá o argumento de linha de comando
 */
int argumento = 0;

/**
 * Declaração da constante do tamanho do arranjo
 */
const int tamanho_total = 100000 + 1;

/**
 * Declaração do arranjo que conterá os números
 */
int arranjo[tamanho_total];

/**
 * Função auxiliar que executa a intercalação dos subarranjos esquerda e
 * direita. Efetua a combinação dos elementos.
 */
void merge(int inicio, int meio, int fim) {

	/**
	 * Calcula e armazena o tamanho do subarranjo da esquerda
	 */
	int tamanho_array_esquerda = meio - inicio + 1;

	/**
	 * Calcula e armazena o tamanho do subarranjo da direita
	 */
	int tamanho_array_direita = fim - meio;

	/**
	 * Criação do subarranjo da esquerda.

	 */
	int array_esquerda[tamanho_array_esquerda + 2];

	/**
	 * Criação do subarranjo da direita
	 */
	int array_direita[tamanho_array_direita + 2];

	/**
	 * Na criação dos subarranjos, soma-se 2 ao valor do tamanho porque deverá
	 * ter uma posição para um elemento sentinela que conterá o maior número
	 * inteiro (MAX) e a posição 0 (zero), essa posição não é utilizada porque o
	 * algoritmo implementa o controle a partir do índice 1 (um), não levando em
	 * consideração a posição zero.
	 */

	/**
	 * Popula o subarranjo da esquerda
	 */
	for (int i = 1; i <= tamanho_array_esquerda; ++i) {
		array_esquerda[i] = arranjo[inicio + i - 1];
	}

	/**
	 * Popula o arranjo da direita
	 */
	for (int j = 1; j <= tamanho_array_direita; ++j) {
		array_direita[j] = arranjo[meio + j];
	}

	/**
	 * Coloca sentinelas nas extremidades dos arranjos.
	 * Os sentinelas servem para informar que um dos subarranjos já foi copiado
	 * por completo para o subarranjo global.
	 */
	array_esquerda[tamanho_array_esquerda + 1] = INT_MAX;
	array_direita[tamanho_array_direita + 1] = INT_MAX;

	/**
	 * Armazena índice inicial do subarranjo da esquerda
	 */
	int ie = 1;

	/**
	 * Armazena índice inicial do subarranjo da direita
	 */
	int id = 1;

	/**
	 * Loop para combinar os elementos dos subarranjos esquerda e direita de
	 * maneira que eles fiquem ordenados
	 */
	for (int k = inicio; k <= fim; ++k) {

		/**
		 * A cada passo do loop, é feito um teste para ver qual é o menor
		 * elemento entre um elemento do subarranjo da esquerda e um elemento do
		 * subarranjo da direita. Em cada passo, após essa verificação, o menor
		 * elemento é copiado para o subarranjo de escopo global, ao qual terá
		 * no final todos elementos ordenados.
		 *
		 * No final do loop, restarão 2 elementos sentinelas, um no subarranjo
		 * da direita e outro no subarranjo da esquerda.
		 */
		if (array_esquerda[ie] <= array_direita[id]) {
			arranjo[k] = array_esquerda[ie]; // copia da esqueda
			ie = ie + 1; // incrementa o índice da esquerda
		} else {
			arranjo[k] = array_direita[id]; // copia da direita
			id = id + 1; // incrementa o índice da direita
		}
	}
}

/**
 * Função merge sort. Recebe como parâmetros os índices de início e fim do
 * subarranjo a ser ordenado.
 *
 * Irá operar sobre o arranjo somente quando o índice de início for menor que o
 * índice do fim passados como argumentos da função.
 */
void merge_sort(int inicio, int fim) {

	/**
	 * Entra no bloco condicional somente se o tamanho do subarranjo for maior
	 * que 1 (um)
	 */
	if (inicio < fim) {
		/**
		 * Armazena o índice que determina o meio do subarranjo.
		 * Etapa DIVIDIR.
		 */
		int meio = (inicio + fim) / 2;

		/**
		 * Chamada recursiva para o subarranjo da esquerda
		 * Etapa CONQUISTAR.
		 */
		merge_sort(inicio, meio);

		/**
		 * Chamada recursiva para o subarranjo da direita
		 * Etapa CONQUISTAR.
		 */
		merge_sort(meio + 1, fim);

		/**
		 * Chamada para intercalar as 2 sequências ordenadas
		 * Etapa COMBINAR.
		 */
		merge(inicio, meio, fim);
	}
}

/**
 * Faz a troca dos elementos no subarranjo baseado nos índices informados nos
 * argumentos.
 */
void quick_troca_valores(int indice_a, int indice_b) {
	int valor_a = arranjo[indice_a]; // armazena o valor do índice A
	int valor_b = arranjo[indice_b]; // armazena o valor do índice B
	arranjo[indice_a] = valor_b; // atribui o valor de B na posição de A
	arranjo[indice_b] = valor_a; // atribui o valor de A na posição de B
}

/**
 * Função de particionamento quick sort. Recebe como parâmetros os índices de 
 * início e fim do subarranjo.
 *
 * Executa a operação que coloca os valores menores ou igual ao pivô na esquerda
 * do pivô no subarranjo (partição esquerda), e os valores maiores que o pivô na
 * direita do pivô no subarranjo (partição direita).
 *
 * A função retorna o índice do pivô, entretanto os valores que ficaram nas
 * partições não estarão necessariamente ordenados.
 *
 * Os valores contidos nas partições serão ordenados pelas chamadas recursivas a
 * quick sort.
 */
int quick_particiona(int inicio, int fim) {

	/**
	 * Pega o valor do pivô (último elemento do subarranjo)
	 */
	int pivo = arranjo[fim];

	/**
	 * Variável que ao final do loop conterá o índice anterior ao índice do pivô
	 */
	int i = inicio - 1;

	/**
	 * Itera x vezes, onde x é o resultado de (fim - 1)
	 * Ex.: Se a variável "fim" vale 5, irá executar 4 vezes as operações de
	 * dentro do loop "for"
	 */
	for (int j = inicio; j <= fim - 1; ++j) {

		/**
		 * Testa se o valor que contém no índice j é menor que o pivô
		 */
		if (arranjo[j] <= pivo) {

			/**
			 * Incrementa o índice
			 */
			i = i + 1;

			/**
			 * Troca os valores das posições "j" e "i"
			 */
			quick_troca_valores(j, i);
		}
	}

	/**
	 * Move o pivô para seu lugar entre as partições. Faz a troca entre o
	 * elemento pivô (fim) com o elemento mais a esquerda no subarranjo que é
	 * maior que o pivô
	 */
	quick_troca_valores(i + 1, fim);

	/**
	 * Retorna o índice do pivô
	 */
	return i + 1;
}

/*
 * Função quick sort. Recebe como parâmetros os índices de início e fim do
 * subarranjo a ser ordenado.
 *
 * Irá operar sobre o arranjo somente quando o índice de início for menor que o
 * índice do fim passados como argumentos da função.
 */
void quick_sort(int inicio, int fim) {

	/**
	 * Entra no bloco condicional somente se o tamanho do subarranjo for maior
	 * que 1 (um)
	 */
	if (inicio < fim) {

		/**
		 * Particiona e pega o índice do pivô
		 */
		int indice_pivo = quick_particiona(inicio, fim);

		/**
		 * Chamada recursiva a quick sort para a partição esquerda (valores a
		 * esquerda do pivô)
		 */
		quick_sort(inicio, indice_pivo - 1);

		/**
		 * Chamada recursiva a quick sort para a partição direita (valores a
		 * direita do pivô)
		 */
		quick_sort(indice_pivo + 1, fim);
	}
}

/**
 * Função que gera um número randômico de 1 ao valor contido na variável
 * "argumento". Ex.: argumento = 10. Gera números randômicos de 1 a 10.
 */
int random_number() {
	return rand() % argumento + 1;
}

/**
 * Imprime no console o subarranjo.
 * Não imprime quando o subarranjo for maior que 20.
 */
void imprime_arranjo() {

	if (argumento < 21) {
		cout << endl;

		for (int var = 1; var <= argumento; ++var) {
			cout << arranjo[var] << " ";
		}

		cout << endl;
	}
}

/**
 * Função principal que é executada quando o programa é invocado pela linha de
 * comando.
 */
int main(int argc, char *argv[]) {

	/**
	 * Captura e armazena o valor informado como argumento pela linha de
	 * comando
	 */
	argumento = atoi(argv[1]);

	cout << "Tamanho do arranjo: " << argumento << endl;

	/**
	 * Inicializa gerador de números randômicos
	 */
	srand(time(NULL));

	/**
	 * Gera números randômicos nas posições do array
	 */
	generate_n(arranjo, tamanho_total, random_number);

	/**
	 * Efetua uma cópia do arranjo
	 */
	int copia_arranjo[tamanho_total];
	for (int i = 0; i < tamanho_total; ++i) {
		copia_arranjo[i] = arranjo[i];
	}

	imprime_arranjo();

	cout << "Tempo Merge Sort: " << endl;
	time_log_start();
	merge_sort(1, argumento); // invoca merge sort
	time_log_stop();

	imprime_arranjo();

	/**
	 * Restaura valores desordenados ao estado inicial
	 */
	for (int i = 0; i < tamanho_total; ++i) {
		arranjo[i] = copia_arranjo[i];
	}

	imprime_arranjo();

	cout << endl << "Tempo Quick Sort: " << endl;
	time_log_start();
	quick_sort(1, argumento); // invoca quick sort
	time_log_stop();

	imprime_arranjo();

	cout << endl;

	return 0;
}
